package leetcode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0079.java
 * @Author : WangRuoyu
 * @Date 2023/11/27 21:28
 */

public class Q0079 {
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};
    
    private boolean dfs(int x, int y, int k, char[][] board, String word, boolean[][] st) {
        if (board[x][y] != word.charAt(k)) return false;
        if (k == word.length() - 1) return true;
        st[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int m = x + dx[i];
            int n = y + dy[i];
            if (m >= 0 && m < board.length && n >= 0 && n < board[0].length && !st[m][n]) {
                if (dfs(x + dx[i], y + dy[i], k + 1, board, word, st)) return true;
            }
        }
        st[x][y] = false;
        return false;
    }

    public boolean exist(char[][] board, String word) {
        boolean[][] st = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(i, j, 0, board, word, st)) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Q0079 sl = new Q0079();
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "ABCB";
        System.out.println(sl.exist(board, word));
    }
}